#include <iostream>
#include <stack>
using namespace std;
#define MVNum 1000//最大顶点数
int visited[MVNum]={0};//判别顶点是否被访问过
typedef struct ArcNode//边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    //OtheInfo info;//边相关的信息（如权值）
}ArcNode;

typedef struct VNode//顶点信息
{ 
    int data;
    ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型为VNode型数组

typedef struct//邻接表
{
    AdjList adjlist;
    int vexnum, arcnum; //图的当前顶点数和边数
}ALG;//邻接表

int LocateVex(ALG G, int v)//邻接表G中v的位置
{
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.adjlist[i].data == v)
           return i;
    }
    return -1;
}

void CreateUDG(ALG &G)//邻接表表示法，创建 无向图G
{
    int i, k, temp;
    cin >> G.vexnum >> G.arcnum;//输入图总顶点数和总边数
    for (i = 1; i <= G.vexnum; i++) // 输入各点，构建 邻接表头结点表,从1开始编号
    {
        cin >> temp;
        G.adjlist[i].data = temp;
        G.adjlist[i].firstarc = NULL; //指向第一条依附该顶点的边的指针,初始化为NULL
    }
    for (k = 0; k < G.arcnum; k++) // 输入各边，构建邻接表
    {
        int v1, v2;
        //char ch;
        //cin >> v1 >> ch >> v2; // 输入一条边的两个顶点
        scanf("%d%d",&v1,&v2);
        int i, j;
        i = LocateVex(G, v1);//确定v1和v2在G中位置i和j，即顶点在G.adjlist中的序号
        j = LocateVex(G, v2);
        ArcNode *p1,*p2;
        p1=new ArcNode;//生成一个新的边结点
        p1->adjvex = j;//该边所指向的顶点的位置为j，即该边的邻接点序号为j
        p1->nextarc = G.adjlist[i].firstarc;
        G.adjlist[i].firstarc = p1;//头插法，把新的边结点插入插入顶点Vi的 邻接边表 的头部
        p2=new ArcNode;//生成一个新的边结点
        p2->adjvex=i;//该边所指向的顶点的位置为i，即该边的邻接点序号为i
        p2->nextarc = G.adjlist[j].firstarc;
        G.adjlist[j].firstarc = p2;//头插法，把新的边结点插入插入顶点Vj的 邻接边表 的头部
    }
}

void DFSAL(ALG G,int v)//深度优先遍历 邻接表 储存的图，从第v个顶点开始
{
    int i, temp;
    stack<int> s;
    ArcNode *p;
    for (i = 1; i <= G.vexnum; i++)
    {
        visited[i] = 0;//初始化访问数组为0
    }
    cout << 'v' << v << ' ';
    s.push(v);
    visited[v] = 1;//标记被访问的点
    while(!s.empty())
    {
        temp = s.top();
        p = G.adjlist[temp].firstarc;//p为第temp个顶点的第一条邻接边
        while(p!=NULL)
        {
           if(visited[p->adjvex]==0)//找到未访问的结点入栈后退出循环
           {
               cout << 'v' << p->adjvex << ' ';
               visited[p->adjvex] = 1;//访问标记
               s.push(p->adjvex);//入未访问的结点编号入栈
               break;
           }
           p = p->nextarc;//p移到下一个边结点
        }
        if(p==NULL)
        s.pop();//栈顶出栈
    }
}

int main()
{
    ALG G;
    CreateUDG(G);
    DFSAL(G,1);
    return 0;
}